1. Technical Field
The present invention is related to computer graphics and more particularly to a system and method for synthesis of parametric texture map (PTM) textures.
2. Background
Various techniques have been utilized to render graphical images via computer systems. One representation of visual images is referred to as a texture. A texture refers to a graphics data structure which models the surface appearance of an object. A texture may represent the visual experience of many materials and substances (e.g., terrain, plants, minerals, fur, and skin). Textures may be created digitally by sampling a physical surface utilizing photographic techniques. Alternatively, textures may be created manually utilizing a suitable graphics design application.
Texture synthesis refers to creating a new texture of a selected size from a sample texture of a fixed size. For example, FIG. 1A depicts exemplary texture 101. Texture 101 includes a distribution of diamonds and stars. Although the diamonds and stars appear to be distributed in a semblance of order, a degree of randomization is apparent. The diamonds and stars seem to be arranged according to a stochastic process. FIG. 1B depicts exemplary synthesized texture 102. Synthesized texture 102 is not merely an enlarged or upscaled version of texture 101. Synthesized texture 102 possesses approximately the same degree of detail per unit of area as texture 101. The distribution of diamonds and stars in synthesized texture 102 does not exactly correspond to the distribution in texture 101. However, it appears that the same stochastic process has generated the distribution of synthesized texture 102.
Synthesizing a new texture that appears to a observer to have been generated from the same stochastic process may be quite challenging. In particular, interpolation techniques (such as Fourier coefficient algorithms) are not helpful, because the level of visual detail as a function of area is not maintained in the larger synthesized texture. Moreover, boundary conditions present a number of difficulties. In particular, seams and repetitions may be visually evident thereby reducing the realism of the synthesized texture.
A texture synthesis algorithm has been developed by Li-Yi Wei and Marc Levoy which addresses the preceding texture synthesis issues. The algorithm is described in Fast Texture Synthesis Using Tree-Structured Vector Quantization, Li-Yi Wei and Marc Levoy, SIGGRAPH 2000 Conference Proceedings, pg. 479-488, which is incorporated herein by reference. The algorithm begins by utilizing a texture of a given size to generate a texture of some arbitrary larger size. Wei and Levoy describe (a) modeling or estimating the stochastic process associated with the original texture and (b) sampling from the original texture to synthesize or produce the new texture having the larger size. At a high level, the algorithm synthesizes the new texture by modeling the original texture using Markov Random Field concepts. The algorithm assembles the new texture in a pixel by pixel manner. Each pixel of the new matrix is determined by comparing its xe2x80x9cneighborhoodxe2x80x9d to all neighborhoods in the original matrix.
Specifically, the synthesis algorithm taught by Wei and Levoy begins by receiving a data structure defining a texture. The data structure is a matrix of red, green, and blue (RGB) values defining the texture, where RGB is a well-known encoding method for representing the red, green, and blue chromatic channels of a pixel. A second matrix is created that is equal in size to the desired size of the texture to be synthesized. The second matrix is initialized with white random noise.
The algorithm proceeds by examining each pixel of the second matrix in raster scan order (e.g., from left to right and top to bottom). The algorithm transforms each pixel by first determining the neighborhood of each pixel. The neighborhood refers to a group of pixels that are relatively adjacent to the respective pixel of the second matrix. Also, the neighborhood is preferably chosen to be causal. Specifically, it is selected so that it only contains pixels that have already been synthesized and not pixels containing noise values. For example, FIG. 1C depicts exemplary matrix 103. Matrix 103 comprises pixel 104 and exemplary neighborhood 105. Neighborhood 105 only contains pixels that are previous to pixel 104 in the raster scan order. It shall be appreciated that this is not always possible. Accordingly, the first few pixels are allowed to contain neighborhoods with noise values. However, after a number of pixels have been synthesized, it is preferred to only utilize causal neighborhoods. Also, when a pixel is selected that is close to an edge of the matrix, the neighborhood may be selected in a toroidal manner, i.e., the neighborhood wraps around to the other side of the matrix.
The value of each respective pixel is assigned by comparing it to each pixel in the original matrix. Specifically, each pixel of the second matrix is assigned the color of the pixel in the original matrix that possesses a neighborhood that most closely matches the respective neighborhood of the pixel to be synthesized. The determination of most-closely matching neighborhoods is performed by utilizing a simple norm (sum of square differences) calculation. For example, R1, G1, B1 may represent the red, green, and blue components or channels of a pixel in a neighborhood of the original or sample texture. R2, G2, B2 may represent the red, green, and blue components or channels of a corresponding pixel in a neighborhood of the texture to be synthesized. The square of the difference equals (R1xe2x88x92R2)2+(G1xe2x88x92G2)2+(B1xe2x88x92B2)2. The sum of the differences then equals the summation of the previous calculation for each pixel pair between the two neighborhoods. The lowest norm corresponds to the most closely matching neighborhood.
Wei and Levoy also describe optimizations to the algorithm. First, multi-resolution synthesis is described to adapt to larger sized neighborhoods. The multi-resolution synthesis operates by building Gaussian pyramids from the original matrix and the noise matrix. A Gaussian pyramid is a hierarchy of low-pass filtered versions of the original image, such that successive levels correspond to lower frequencies. The Gaussian pyramid is produced by low-pass filtering via convolution with a Gaussian filter kernel. Although Gaussian pyramids are described, other pyramid or multi-resolution data structures may be utilized in lieu thereof. The algorithm proceeds by transforming the noise Gaussian pyramid from lower to higher resolutions. The only modification for the multi-resolution case is that each neighborhood contains pixels in the current resolution and all lower resolutions.
Wei and Levoy further describe acceleration of the algorithm utilizing tree-structured vector quantization (TSVQ). As described in Vector Quantization and Signal Compression, A. Gersho and R. M. Gray (1992), which is incorporated herein by reference, TSVQ is a well-known technique for data compression. The tree generated by TSVQ may be used as a data structure for efficient nearest-point queries. To find the nearest point of a given query vector, the tree is traversed from the root in a best-first ordering by comparing the query vector with the two children codewords and then following the one that has a closer codeword. This process is repeated for each visited node until a leaf node is reached. The best codeword is then returned as the codeword of that leaf node. Unlike full searching, the result codeword may not be the best or closest one, since only part of the tree is traversed. However, the result codeword usually approximates the exact solution, and the computation is more efficient than full searching.
To use TSVQ in the synthesis algorithm, the set of neighborhood pixels are collected for each input pixel and treated as a vector of a size equal to the number of pixels in the neighborhood. The vectors for each neighborhood are used as the training data to generate the corresponding tree structure codewords. During the synthesis process, the (approximate) closest point neighborhood is found by performing a best-first traversal of the binary-tree structure.
By utilizing the preceding techniques described by Wei and Levoy, texture synthesis may be performed with relatively appreciable quality. Specifically, textures of significant size may be produced from relatively small sample textures. Moreover, the subjective visual quality of the synthesized textures remains comparable to the original samples.
However, the algorithm described by Wei and Levoy contains certain limitations. Specifically, the data structure (RGB matrix) utilized to represent the texture is relatively simple. It does not facilitate modeling of relatively complex visual effects. For example, the RGB representation does not facilitate appreciable perception of surface deformations. Also, the RGB representation does not account for self-shadowing or interreflections. Optical effects such as anisotropic and Frensel shading models are not supported by the RGB representation.
In one embodiment, the present invention is directed to method for assigning coefficients to a texel of a parametric texture map (PTM) texture. The method may comprise the steps of: generating a random PTM matrix of a desired size, the random PTM matrix comprising texels possessing random valued coefficients; selecting a texel from the random PTM matrix; determining a first neighborhood of the texel from the random PTM matrix; comparing the first neighborhood to neighborhoods of a sample PTM texture to determine an optimal texel of the sample PTM texture; and assigning PTM coefficients of the optimal texel to the texel from the random PTM matrix.